package Offer;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class p32从上到下打印二叉树III {
      public class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
      }
    class Solution {
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<>();
            LinkedList<TreeNode> nodes = new LinkedList<>();
            nodes.add(root);
            boolean flag = true;
            while(!nodes.isEmpty()){
                int size = nodes.size();
                LinkedList<Integer> tmp = new LinkedList<>();
                for (int i = 0; i < size; i++) {
                    TreeNode treeNode = nodes.removeFirst();
                    if (flag){ // 奇数层【左到右】
                        tmp.addLast(treeNode.val);
                    } else { // 偶数层【右到左】
                        tmp.addFirst(treeNode.val);
                    }
                    if (treeNode.left != null) nodes.add(treeNode.left);
                    if (treeNode.right != null) nodes.add(treeNode.right);
                }
                res.add(tmp);
                flag = !flag;
            }
            return res;
        }
    }
}
